package demo_11_10;/*
 *@ 代阳敲的专属代码
 **/

import java.util.Stack;

public class test1 {
   static class  ListNode {
      int val;
      ListNode next;
      ListNode() {}
     ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
    public static void main(String[] args) {
       ListNode l1 =new ListNode(9);
//       ListNode l11 =new ListNode(4);
//       ListNode l111 =new ListNode(3);
//       l1.next=l11;
//       l11.next=l111;

        // 构造数字[1,9,9,9,9,9,9,9,9,9]
        ListNode l2 = new ListNode(1);
        ListNode current = l2;
        for (int i = 0; i < 9; i++) {
            current.next = new ListNode(9);
            current = current.next;
        }

        //构造 1,2,3,4
        ListNode l3 = new ListNode(1);
        ListNode l3Current = l3;
        for (int i = 2; i <= 2; i++) {
            l3Current.next = new ListNode(i);
            l3Current = l3Current.next;
        }


       reorderList2(l3);



    }
    public static void reorderList2(ListNode head) {
        //找中心点
        ListNode fast=head;
        ListNode slow=head;

        while(fast!=null&&fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }
        //断开
        fast=slow;
        slow.next=null;
        // 反转
        fast=reverse(fast);


        //合并
       merge(head,  fast);

    }
    public static ListNode reverse(ListNode fast) {
        ListNode cur=fast;
        ListNode newHead =new ListNode(0);
        while(cur!=null) {
            ListNode temp=cur.next;
            cur.next=newHead;
            newHead=cur;
            cur=temp;
        }
        fast.next=null;
        return newHead;
    }
    public static  void merge(ListNode slow,ListNode fast) {
       ListNode head=slow;

        while(fast!=null) {
            ListNode slowtemp=slow.next;
            ListNode fasttemp=fast.next;
            slow.next=fast;
            fast.next=slowtemp;
            fast=fasttemp;
            slow=slowtemp;

        }

    }

    public static void reorderList(ListNode head) {
        if(head==null) return;
        ListNode newHead=new ListNode();
        newHead.next=head;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }
        fast=slow.next;
        slow.next=null;
        //反转
        ListNode fh=fast;
        while(fast.next!=null) {
            fh=fast.next;
            ListNode temp=fh;
            fast.next=temp.next;
            fh.next=fast;

        }
        ListNode cur=head;

        while(fh!=null) {
            ListNode temp1=cur.next;
            ListNode temp2=fh;
            fh=fh.next;
            cur.next=temp2;
            temp2.next=temp1;
            cur=temp1;
        }
    }
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1.val==0) return l2;
        if(l2.val==0) return l1;
        ListNode head1=new ListNode();
        ListNode head2=new ListNode();
        head1.next=l1;
        head2.next=l2;
        long count=1;
        long sum1=0;
        while(head1.next!=null) {
            sum1+=count*head1.next.val;
            head1=head1.next;
            count=10*count;
        }

        count=1;
        long sum2=0;
        while(head2.next!=null) {
            sum2+=count*head2.next.val;
            head2=head2.next;
            count=10*count;
        }
        long sum3=sum1+sum2;
        ListNode head3=new ListNode();
        ListNode tail=head3;
        while(sum3!=0) {
            long x=sum3%10;

            ListNode node=new ListNode((int) x);
            tail.next=node;
            tail=node;
            sum3=sum3/10;
        }
        return head3.next;

    }
    public static boolean isValid(String s) {
        char [] ca= s.toCharArray();
        Stack<Character> stack =new Stack<Character>() ;
        for(int i=0;i<s.length();i++) {
            if(ca[i]=='('||ca[i]=='{'||ca[i]=='[') {
                stack.push(ca[i]);
            }else {
                char x=ca[i];
                switch(x) {
                    case  ')' :
                        if(stack.peek()=='(')  {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;
                    case  '}' :
                        if(stack.peek()=='{')  {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;
                    case  ']' :
                        if(stack.peek()=='[')  {
                            stack.pop();
                        } else {
                            return false;
                        }
                        break;
                }
            }
        }
       return  stack.empty();
    }

    public static int[] sortArrayByParity(int[] nums) {
        int left=0,right=nums.length-1;
        while(left<right) {
            if(nums[left]%2==0) left++;
            while(nums[right]%2==1) right--;
            if(nums[left]%2!=0&&nums[right]%2!=1) {
                int temp =nums[left];
                nums[left]=nums[right];
                nums[right]=temp;

            }
        }
        return nums;
    }

    public static int minOperations(int[] nums, int x) {
        int temp=0;
        for(int i=0;i<nums.length;i++) {
            temp +=nums[i];
        }
        int taget=temp-x;
        if(taget<0) {
            return -1;
        }
        int left=0;
        int right=0;
        int sum=0;
        int len=-1;
        while(right<nums.length) {

            sum+=nums[right];

            if(sum==taget) {
                len=Math.max(len,right-left+1);
            }
            while(sum>=taget&&left<right) {
                sum-=nums[left++];
            }
            right++;
        }
        return len==-1?-1:nums.length-len;

    }

}
